Audio fingerprint matching is a process that may be used to identify songs or other items of recorded audio content. For example, a user may use an application executing on a mobile device (e.g., a cellular telephone) to record a segment of a song that the user wishes to identify. The mobile application may compare (or may cause a server to compare) the recorded audio segment to known audio segments in a database to identify the song.
To determine whether an unknown audio segment matches a known audio segment, an ordered comparison between the segments may be performed. Performing the ordered comparison may include selecting a portion of the known audio segment and comparing the selected portion to each portion of the unknown audio segment. When a match is detected, neighboring (i.e., temporally adjacent) portions of the audio segments may be compared in an attempt to “grow” the match backwards and forwards in time. For example, if the initially selected portion of the unknown audio segment is denoted U and its matching portion in the known audio segment is denoted K, growing the match includes comparing portion U−1 with portion K−1 and portion U+1 with portion K+1, comparing portion U−2 with portion K−2 and portion U+2 with portion K+2, etc. If enough of the neighboring portions also match (i.e., the match grows past a threshold amount), an overall match between the known and unknown audio segments is determined.
However, if the unknown audio segment recorded by the user has noise or distortion, the wrong song, or no song, may be identified. Further, if the version of the song recorded by the user is time-stretched or time-squeezed, ordered matching processes may not correctly identify the song, even though the song is in the database. Such time-stretching or time-squeezing may be introduced by radio stations so that a song or sequence of songs fits into a fixed duration of time. Time-stretching or time-squeezing may also occur due to natural differences between live performances and recorded songs. In addition, performing ordered comparisons may consume a large amount of processing resources and the database of known songs may occupy a large amount of memory.